package main.leetcode.offer.firstround.from03to50;

import main.datastruc.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 37.序列化二叉树
 *
 * <p>请实现两个函数，分别用来序列化和反序列化二叉树。
 */
public class ex37 {
    public static void main(String[] args) {
        ex37 ex = new ex37();
        TreeNode root = ex.deserialize("5 2 null null 3 2 3 null null 1 null null 4 null null");
        System.out.println(new ex37().serialize(root));
    }

    /** 层序遍历 */
    //  // Encodes a tree to a single string.
    //  public String serialize(TreeNode root) {
    //    if (root == null) return "";
    //    StringBuilder s = new StringBuilder();
    //    Queue<TreeNode> queue = new LinkedList<>();
    //    queue.add(root);
    //    TreeNode node;
    //    while (!queue.isEmpty()) {
    //      node = queue.remove();
    //      if (node == null) s.append("null ");
    //      else {
    //        s.append(node.val).append(" ");
    //        queue.add(node.left);
    //        queue.add(node.right);
    //      }
    //    }
    //    return s.toString();
    //  }
    //  // Decodes your encoded data to tree.
    //  public TreeNode deserialize(String data) {
    //    if (data.length() < 1 || data.charAt(0) == 'n') return null;
    //    String[] nums = data.split(" ");
    //    Queue<TreeNode> queue = new LinkedList<>();
    //    int i = 1;
    //    TreeNode root = new TreeNode(Integer.parseInt(nums[0]));
    //    queue.add(root);
    //    TreeNode node;
    //    while (i < nums.length && !queue.isEmpty()) {
    //      node = queue.poll();
    //      if (node == null) continue;
    //      node.left = "null".equals(nums[i]) ? null : new TreeNode(Integer.parseInt(nums[i]));
    //      node.right = "null".equals(nums[i + 1]) ? null : new TreeNode(Integer.parseInt(nums[i +
    // 1]));
    //      i += 2;
    //      queue.add(node.left);
    //      queue.add(node.right);
    //    }
    //    return root;
    //  }

    /** 深度遍历 */
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder data = new StringBuilder();
        dfs(root, data);
        return data.toString();
    }

    private void dfs(TreeNode root, StringBuilder data) {
        if (root == null) data.append("null ");
        else {
            data.append(root.val).append(" ");
            dfs(root.left, data);
            dfs(root.right, data);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nums = data.split(" ");
        List<String> list = new ArrayList<>(Arrays.asList(nums));
        return dfs(list);
    }

    private TreeNode dfs(List<String> data) {
        if ("null".equals(data.get(0))) {
            data.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(data.get(0)));
        data.remove(0);
        root.left = dfs(data);
        root.right = dfs(data);
        return root;
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
